<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>Redis数据结构-字典 | Oliver知识收集站</title>
    <meta name="generator" content="VuePress 1.9.7">
    
    <meta name="description" content="享受着互联网广泛知识，并加以记录，日积月累让它成为一个档案处！">
    <meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no">
    
    <link rel="preload" href="/oliver-vuepress/assets/css/0.styles.4ea20d86.css" as="style"><link rel="preload" href="/oliver-vuepress/assets/js/app.c21e6ffc.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/3.6dd9a2a1.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/1.898920d0.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/54.6569f7db.js" as="script"><link rel="prefetch" href="/oliver-vuepress/assets/js/10.41b2bf91.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/11.a95c117d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/12.8607f0e1.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/13.a52d6846.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/14.249b4e52.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/15.d458d12e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/16.ba334206.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/17.1b91c9fa.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/18.e2ea2eb5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/19.bf0e2553.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/20.268bd174.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/21.cd1bbed5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/22.da4bc7f7.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/23.12f0c72f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/24.b7886742.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/25.6e71af85.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/26.5c127243.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/27.e98fd8bf.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/28.ce83b09c.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/29.50398f0f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/30.05e1339c.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/31.ef4b13fb.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/32.ba5f8351.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/33.3902db0a.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/34.36a05884.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/35.87215872.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/36.db360c58.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/37.402e5374.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/38.c9228dd8.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/39.72ba5d1f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/4.7bb03d47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/40.7e7949bf.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/41.c0d5b947.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/42.d9984467.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/43.e6a43668.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/44.10d7fe47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/45.f692ec2d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/46.9b920343.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/47.8e3d94f9.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/48.7d356e5b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/49.b0df6271.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/5.1fa544da.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/50.805e1466.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/51.1b31d40e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/52.44e69a41.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/53.da1def53.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/55.5fc3de47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/56.da649377.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/57.6ff15ed4.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/58.a62f6424.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/59.f68ae517.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/6.f5bd8e9b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/60.dda416bc.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/61.4e0c719f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/62.8c5ef01e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/63.7089eb8b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/64.b5ec150d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/65.6720cda4.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/66.4ee90e29.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/67.cc4b0c6d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/7.d5950c53.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/8.382fb3a5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/9.d593f4c1.js">
    <link rel="stylesheet" href="/oliver-vuepress/assets/css/0.styles.4ea20d86.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container no-sidebar" data-v-130b300a><div data-v-130b300a><div class="password-shadow password-wrapper-out" style="display:none;" data-v-25ba6db2 data-v-130b300a data-v-130b300a><h3 class="title" data-v-25ba6db2 data-v-25ba6db2>Oliver知识收集站</h3> <p class="description" data-v-25ba6db2 data-v-25ba6db2>享受着互联网广泛知识，并加以记录，日积月累让它成为一个档案处！</p> <label id="box" class="inputBox" data-v-25ba6db2 data-v-25ba6db2><input type="password" value="" data-v-25ba6db2> <span data-v-25ba6db2>Konck! Knock!</span> <button data-v-25ba6db2>OK</button></label> <div class="footer" data-v-25ba6db2 data-v-25ba6db2><span data-v-25ba6db2><i class="iconfont reco-theme" data-v-25ba6db2></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-25ba6db2>vuePress-theme-reco</a></span> <span data-v-25ba6db2><i class="iconfont reco-copyright" data-v-25ba6db2></i> <a data-v-25ba6db2><span data-v-25ba6db2>oliver.shi</span>
            
          <!---->
          2022
        </a></span></div></div> <div class="hide" data-v-130b300a><header class="navbar" data-v-130b300a><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/oliver-vuepress/" class="home-link router-link-active"><!----> <span class="site-name">Oliver知识收集站</span></a> <div class="links"><div class="color-picker"><a class="color-button"><i class="iconfont reco-color"></i></a> <div class="color-picker-menu" style="display:none;"><div class="mode-options"><h4 class="title">Choose mode</h4> <ul class="color-mode-options"><li class="dark">dark</li><li class="auto active">auto</li><li class="light">light</li></ul></div></div></div> <div class="search-box"><i class="iconfont reco-search"></i> <input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/oliver-vuepress/" class="nav-link"><i class="undefined"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      Java
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/basics/" class="nav-link"><i class="undefined"></i>
  基础
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/concurrent/" class="nav-link"><i class="undefined"></i>
  并发
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/jvm/jvm.html" class="nav-link"><i class="undefined"></i>
  JVM
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/other/" class="nav-link"><i class="undefined"></i>
  杂
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/spring/first.html" class="nav-link"><i class="undefined"></i>
  Spring
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      中间件
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/redis/redis.html" class="nav-link"><i class="undefined"></i>
  Redis
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/kafka/framework.html" class="nav-link"><i class="undefined"></i>
  Kafka
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/zookeeper.html" class="nav-link"><i class="undefined"></i>
  Zookeeper
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/algorithm/" class="nav-link"><i class="undefined"></i>
  算法
</a></div><div class="nav-item"><a href="/oliver-vuepress/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  TimeLine
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      收集站
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/article/first.html" class="nav-link"><i class="undefined"></i>
  技术好文
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/book/first.html" class="nav-link"><i class="undefined"></i>
  书籍
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/assembly/first.html" class="nav-link"><i class="undefined"></i>
  优秀开发组件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/software/first.html" class="nav-link"><i class="undefined"></i>
  软件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/plugin/first.html" class="nav-link"><i class="undefined"></i>
  插件
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask" data-v-130b300a></div> <aside class="sidebar" data-v-130b300a><div class="personal-info-wrapper" data-v-39576ba9 data-v-130b300a><!----> <h3 class="name" data-v-39576ba9>
    oliver.shi
  </h3> <div class="num" data-v-39576ba9><div data-v-39576ba9><h3 data-v-39576ba9>52</h3> <h6 data-v-39576ba9>Articles</h6></div> <div data-v-39576ba9><h3 data-v-39576ba9>6</h3> <h6 data-v-39576ba9>Tags</h6></div></div> <ul class="social-links" data-v-39576ba9></ul> <hr data-v-39576ba9></div> <nav class="nav-links"><div class="nav-item"><a href="/oliver-vuepress/" class="nav-link"><i class="undefined"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      Java
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/basics/" class="nav-link"><i class="undefined"></i>
  基础
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/concurrent/" class="nav-link"><i class="undefined"></i>
  并发
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/jvm/jvm.html" class="nav-link"><i class="undefined"></i>
  JVM
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/other/" class="nav-link"><i class="undefined"></i>
  杂
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/spring/first.html" class="nav-link"><i class="undefined"></i>
  Spring
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      中间件
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/redis/redis.html" class="nav-link"><i class="undefined"></i>
  Redis
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/kafka/framework.html" class="nav-link"><i class="undefined"></i>
  Kafka
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/zookeeper.html" class="nav-link"><i class="undefined"></i>
  Zookeeper
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/algorithm/" class="nav-link"><i class="undefined"></i>
  算法
</a></div><div class="nav-item"><a href="/oliver-vuepress/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  TimeLine
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      收集站
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/article/first.html" class="nav-link"><i class="undefined"></i>
  技术好文
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/book/first.html" class="nav-link"><i class="undefined"></i>
  书籍
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/assembly/first.html" class="nav-link"><i class="undefined"></i>
  优秀开发组件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/software/first.html" class="nav-link"><i class="undefined"></i>
  软件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/plugin/first.html" class="nav-link"><i class="undefined"></i>
  插件
</a></li></ul></div></div> <!----></nav> <!----> </aside> <div class="password-shadow password-wrapper-in" style="display:none;" data-v-25ba6db2 data-v-130b300a><h3 class="title" data-v-25ba6db2 data-v-25ba6db2>Redis数据结构-字典</h3> <!----> <label id="box" class="inputBox" data-v-25ba6db2 data-v-25ba6db2><input type="password" value="" data-v-25ba6db2> <span data-v-25ba6db2>Konck! Knock!</span> <button data-v-25ba6db2>OK</button></label> <div class="footer" data-v-25ba6db2 data-v-25ba6db2><span data-v-25ba6db2><i class="iconfont reco-theme" data-v-25ba6db2></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-25ba6db2>vuePress-theme-reco</a></span> <span data-v-25ba6db2><i class="iconfont reco-copyright" data-v-25ba6db2></i> <a data-v-25ba6db2><span data-v-25ba6db2>oliver.shi</span>
            
          <!---->
          2022
        </a></span></div></div> <div data-v-130b300a><main class="page"><section><div class="page-title"><h1 class="title">Redis数据结构-字典</h1> <div data-v-f875f3fc><i class="iconfont reco-account" data-v-f875f3fc><span data-v-f875f3fc>oliver.shi</span></i> <i class="iconfont reco-date" data-v-f875f3fc><span data-v-f875f3fc>4/20/2022</span></i> <!----> <i class="tags iconfont reco-tag" data-v-f875f3fc><span class="tag-item" data-v-f875f3fc>Redis</span></i></div></div> <div class="theme-reco-content content__default"><blockquote><p>字典,又称为 <code>符号表(symbol table)</code>、<code>关联数组(associative array)</code>或 <code>映射(map)</code>,是一种用于保存键值对<code>(key-value pair)</code> 的抽象数据结构。当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现</p></blockquote> <h2 id="基本数据结构"><a href="#基本数据结构" class="header-anchor">#</a> 基本数据结构</h2> <img src="/oliver-vuepress/middleware/redislearn/redis字典.png" alt="foo"> <div class="language-C extra-class"><pre class="language-c"><code>dict<span class="token punctuation">.</span>h<span class="token operator">/</span>dict
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">dict</span><span class="token punctuation">{</span>
  <span class="token comment">//  类型特定函数</span>
  dictType <span class="token operator">*</span>type<span class="token punctuation">;</span>
  <span class="token comment">//  私有数据，提供给 dictType 中函数的参数</span>
  <span class="token keyword">void</span> <span class="token operator">*</span>privdata<span class="token punctuation">;</span>
  <span class="token comment">//  哈希表</span>
  dictht ht<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span>
  <span class="token comment">// rehash 索引，当 rehash 不在进行时，值为 ‑ 1</span>
  <span class="token keyword">int</span> trehashidx<span class="token punctuation">;</span>
<span class="token punctuation">}</span> dict

<span class="token macro property"><span class="token directive-hash">#</span> <span class="token directive keyword">dict</span><span class="token expression">的两个哈希表</span></span>
dict<span class="token punctuation">.</span>h<span class="token operator">/</span>dictht
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">dictht</span><span class="token punctuation">{</span>
  <span class="token comment">//  哈希表数组</span>
  dictEntry <span class="token operator">*</span><span class="token operator">*</span>table<span class="token punctuation">;</span>
  <span class="token comment">//  哈希表大小</span>
  <span class="token keyword">unsigned</span> <span class="token keyword">long</span> size<span class="token punctuation">;</span>
  <span class="token comment">//  哈希表大小掩码，用于计算索引值，总是等于 size ‑ 1</span>
  <span class="token keyword">unsigned</span> <span class="token keyword">long</span> sizemark<span class="token punctuation">;</span>
  <span class="token comment">//  该哈希表已有节点的数量</span>
  <span class="token keyword">unsigned</span> <span class="token keyword">long</span> used<span class="token punctuation">;</span>
<span class="token punctuation">}</span> dictht
  
# 对应 dict 中的 type 值
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">dictType</span><span class="token punctuation">{</span>
  <span class="token comment">//  计算哈希值的函数</span>
  <span class="token keyword">unsigned</span> <span class="token keyword">int</span> <span class="token punctuation">(</span><span class="token operator">*</span>hashFunction<span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">void</span> <span class="token operator">*</span>key<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//  复制键的函数</span>
  <span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">(</span><span class="token operator">*</span>keyDup<span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>privdata<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">void</span> <span class="token operator">*</span>key<span class="token punctuation">)</span>  
  <span class="token comment">//  复制值的函数</span>
  <span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">(</span><span class="token operator">*</span>valDup<span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>privdata<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">void</span> <span class="token operator">*</span>obj<span class="token punctuation">)</span>  
  <span class="token comment">//  对比键的函数</span>
  <span class="token comment">//  销毁键的函数</span>
  <span class="token comment">//  销毁值的函数</span>
<span class="token punctuation">}</span> dictType

 <span class="token macro property"><span class="token directive-hash">#</span> <span class="token directive keyword">hash</span> <span class="token expression">表中的元素节点</span></span>
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">dictEntry</span><span class="token punctuation">{</span>
  <span class="token comment">//  键</span>
  <span class="token keyword">void</span> <span class="token operator">*</span>key<span class="token punctuation">;</span>
  <span class="token comment">//  值</span>
  <span class="token keyword">union</span> <span class="token punctuation">{</span>
    <span class="token keyword">void</span> <span class="token operator">*</span>val<span class="token punctuation">;</span>
    uint64_u64<span class="token punctuation">;</span>
    <span class="token class-name">int64_t</span> s64<span class="token punctuation">;</span>
  <span class="token punctuation">}</span> v<span class="token punctuation">;</span>
  <span class="token comment">//  指向下个哈希表节点，形成链表</span>
  <span class="token keyword">struct</span> <span class="token class-name">dictEntry</span> <span class="token operator">*</span>next<span class="token punctuation">;</span>
<span class="token punctuation">}</span>  dictEntry
</code></pre></div><p><strong>为什么字典中的 哈希表定义2个</strong>？</p> <p>一般情况下,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0] 哈希表进行rehash时使用</p> <p><strong>字典中 <code>rehashidx</code>  属性的作用</strong></p> <ul><li>-1：没有 rehash</li> <li>0： 开始 rehash
<ul><li>每执行完一个 rehashidx+1</li></ul></li> <li>-1:    完成 rehash</li></ul> <h2 id="哈希算法"><a href="#哈希算法" class="header-anchor">#</a> 哈希算法</h2> <p><strong>如何计算索引位</strong>：</p> <p>1 . 计 算 key 的 <code>哈希值</code> ；
2 . 使 用 <code>哈希表</code> 的 sizemask + <code>哈希值</code> ，计算出 <code>索引位置</code> ;
3 . 如果出现 Hash 冲突， Redis 是使用<code>拉链法来</code> 解决的，新的值会成为<code>链表头节点</code>。</p> <blockquote><p>Redis 使用的是 MurmuHash2 的算法来计算哈希值的，该算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法
的计算速度也非常快</p></blockquote> <h2 id="rehash"><a href="#rehash" class="header-anchor">#</a> Rehash</h2> <blockquote><p>由于 哈希表 保存的数量 太多 或者 太少时，需要对哈希表 进行 扩展 或 收缩，这个时候需要rehash</p></blockquote> <p><strong>Rehash的步骤</strong></p> <ul><li>为字典的ht[1]哈希表分配空间；</li> <li>将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上；</li> <li>当ht[0]包含的所有键值对放置到ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备</li></ul> <p><strong>哈希表的扩展与收缩（即触发Rehash操作的时机）</strong></p> <p><strong>核心是通过负载因子来判断触发的时机</strong>计算负载因子的公式： ht[0].used / ht[0]size</p> <ul><li><p>当一下条件任意一个被满足时，开始对哈希表执行扩展操作</p> <ul><li><p>服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于1；</p></li> <li><p>服务器目前在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大5；</p></li></ul></li> <li><p>当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。</p></li></ul> <h3 id="渐进试rehash"><a href="#渐进试rehash" class="header-anchor">#</a> 渐进试Rehash</h3> <blockquote><p>如果哈希表里保存的键值对数量不是四个,而是四百万、四千万甚至四亿个键值对,那么要一次性将这些键值对全部rehash到ht[1]的话,庞大的计算量可能会导致服务器在一段时间内停止服务.</p> <p><strong>这个rehash动作并不是一次性、集中式地完成的,而是分多次、渐进式地完成的</strong></p></blockquote> <p>步骤：</p> <ul><li><p>为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。</p></li> <li><p>rehash 开始时，将 rehashidx 设置为 0</p></li> <li><p>在rehash 进行期间</p> <ul><li>对字典执行添加、删除、查找或者更新操作时 都将写入 ht[1]</li> <li>将 ht[0] 键 移动到 ht[1]，每次执行 rehashidx状态位+1</li> <li>当 ht[0]全部移动到ht[1]后，rehashidx回到‑1；</li></ul></li> <li><p>当出现读写时，如果发现rehashidx不为‑1，则将当前被读写的元素进行rehash。</p></li></ul></div></section> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新: </span> <span class="time">4/21/2022, 8:17:59 AM</span></div></footer> <!----> <div class="comments-wrapper"><!----></div> <ul class="side-bar sub-sidebar-wrapper" style="width:12rem;" data-v-cb1513f6><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/middleware/redis/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%AD%97%E5%85%B8.html#基本数据结构" class="sidebar-link reco-side-基本数据结构" data-v-cb1513f6>基本数据结构</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/middleware/redis/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%AD%97%E5%85%B8.html#哈希算法" class="sidebar-link reco-side-哈希算法" data-v-cb1513f6>哈希算法</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/middleware/redis/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%AD%97%E5%85%B8.html#rehash" class="sidebar-link reco-side-rehash" data-v-cb1513f6>Rehash</a></li><li class="level-3" data-v-cb1513f6><a href="/oliver-vuepress/articles/middleware/redis/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%AD%97%E5%85%B8.html#渐进试rehash" class="sidebar-link reco-side-渐进试rehash" data-v-cb1513f6>渐进试Rehash</a></li></ul></main> <!----></div></div></div></div><div class="global-ui"><div class="back-to-ceiling" style="right:1rem;bottom:6rem;width:2.5rem;height:2.5rem;border-radius:.25rem;line-height:2.5rem;display:none;" data-v-c6073ba8 data-v-c6073ba8><svg t="1574745035067" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="5404" class="icon" data-v-c6073ba8><path d="M526.60727968 10.90185116a27.675 27.675 0 0 0-29.21455937 0c-131.36607665 82.28402758-218.69155461 228.01873535-218.69155402 394.07834331a462.20625001 462.20625001 0 0 0 5.36959153 69.94390903c1.00431239 6.55289093-0.34802892 13.13561351-3.76865779 18.80351572-32.63518765 54.11355614-51.75690182 118.55860487-51.7569018 187.94566865a371.06718723 371.06718723 0 0 0 11.50484808 91.98906777c6.53300375 25.50556257 41.68394495 28.14064038 52.69160883 4.22606766 17.37162448-37.73630017 42.14135425-72.50938081 72.80769204-103.21549295 2.18761121 3.04276886 4.15646224 6.24463696 6.40373557 9.22774369a1871.4375 1871.4375 0 0 0 140.04691725 5.34970492 1866.36093723 1866.36093723 0 0 0 140.04691723-5.34970492c2.24727335-2.98310674 4.21612437-6.18497483 6.3937923-9.2178004 30.66633723 30.70611158 55.4360664 65.4791928 72.80769147 103.21549355 11.00766384 23.91457269 46.15860503 21.27949489 52.69160879-4.22606768a371.15156223 371.15156223 0 0 0 11.514792-91.99901164c0-69.36717486-19.13165746-133.82216804-51.75690182-187.92578088-3.42062944-5.66790279-4.76302748-12.26056868-3.76865837-18.80351632a462.20625001 462.20625001 0 0 0 5.36959269-69.943909c-0.00994388-166.08943902-87.32547796-311.81420293-218.6915546-394.09823051zM605.93803103 357.87693858a93.93749974 93.93749974 0 1 1-187.89594924 6.1e-7 93.93749974 93.93749974 0 0 1 187.89594924-6.1e-7z" p-id="5405" data-v-c6073ba8></path><path d="M429.50777625 765.63860547C429.50777625 803.39355007 466.44236686 1000.39046097 512.00932183 1000.39046097c45.56695499 0 82.4922232-197.00623328 82.5015456-234.7518555 0-37.75494459-36.9345906-68.35043303-82.4922232-68.34111062-45.57627738-0.00932239-82.52019037 30.59548842-82.51086798 68.34111062z" p-id="5406" data-v-c6073ba8></path></svg></div></div></div>
    <script src="/oliver-vuepress/assets/js/app.c21e6ffc.js" defer></script><script src="/oliver-vuepress/assets/js/3.6dd9a2a1.js" defer></script><script src="/oliver-vuepress/assets/js/1.898920d0.js" defer></script><script src="/oliver-vuepress/assets/js/54.6569f7db.js" defer></script>
  </body>
</html>
